import java.util.*;

public class Main {
    static Random rn = new Random(System.currentTimeMillis());
    public static int getRandomInt(int i){
        return Math.abs(rn.nextInt())%i + 1;
    }

    public void testCustomized(){
        TreeNode r = new TreeNode(10);

        TreeNode rr = new TreeNode(2);
        TreeNode rl = new TreeNode(9);

        r.left = rl;
        r.right = rr;

        TreeNode rrl = new TreeNode(4);
        TreeNode rrr = new TreeNode(8);

        rr.left = rrl;
        rr.right = rrr;

        TreeNode rrrl = new TreeNode(5);
        rrr.left = rrrl;


        testWithTree(null);
        testWithTree(new TreeNode(1));
        testWithTree(r);
    }

    public TreeNode generateTree(int level){
        if(level==0){
            return null;
        }
        TreeNode root = new TreeNode(getRandomInt(50));
        if (getRandomInt(60)>20){
            root.left = generateTree(level -1);
        }
        if(getRandomInt(60)>20) {
            root.right = generateTree(level - 1);
        }
        return root;
    }

    public void test(){
        TreeNode root = generateTree(getRandomInt(12));
        testWithTree(root);
    }

    public void testWithTree(TreeNode root){
        Solution solution = new Solution();

        int[] expected = printTree(root);
        int[] actual = solution.printTree(root);
        if(!Arrays.equals(actual, expected)){
            String msg = "Test Failed\n";
            msg += "Input:" + root.toString() + "\n";
            msg += "Expected:" + Arrays.toString(expected) + "\n";
            msg += "Actual:" + Arrays.toString(actual);
            //System.out.println(msg);
            throw new RuntimeException(msg);
        }
    }

    public int[] printTree(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        int flag = 1;
        if(root == null)
            return new int[0];
        s2.push(root);
        while(!s1.isEmpty() || !s2.isEmpty()){
            if(flag % 2 != 0){
                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    resultList.add(node.val);
                    if(node.left != null){
                        s1.push(node.left);
                    }
                    if(node.right != null){
                        s1.push(node.right);
                    }
                }
            }
            if(flag % 2 == 0){
                while(!s1.isEmpty()){
                    TreeNode node = s1.pop();
                    resultList.add(node.val);
                    if(node.right != null){
                        s2.push(node.right);
                    }
                    if(node.left != null){
                        s2.push(node.left);
                    }
                }
            }
            flag ++;
        }
        return resultList.stream().mapToInt(i->i).toArray();
    }

    public static void main(String[] args) {
        try {
            Main main = new Main();
            main.testCustomized();
            for (int i = 0; i < 20; i++) {
                main.test();
            }
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            System.exit(-1);
        }
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }

    public String toString() {
        StringBuilder buffer = new StringBuilder(50);
        print(buffer, "", "");
        return buffer.toString();
    }

    private void print(StringBuilder buffer, String prefix, String childrenPrefix) {

    }
}
